package ljl.alg.wangzheng_camp.round1.tree;

import java.util.LinkedList;

/**
 * 输入: [1,6,3,2,5]
 * 输出: false
 *
 * 输入: [1,3,2,6,5]
 * 输出: true
 * */
public class _offer33_verify_postorder {
    
    /*
    * 从后往前，递增的部分，是右子树；递减的是左子树
    * 递减后不能再有比根大了！
    * 这样验证吧就，比较 naive 的一个解法
    * */
    class wrong {
        int[] post;
        public boolean verifyPostorder(int[] postorder) {
            post = postorder;
            return recur(0, post.length - 1);
        }
        boolean recur(int from, int to) {
            if (from >= to) return true; // 除非你非常自信，时，用等号，否则用 >=
            int mid = to;
            while (mid > from && post[mid - 1] > post[to]) mid--;
            int p = mid-1;
            while (p >= from) {
                if (post[p] > post[to]) return false;
                p--;
            }
            return recur(from, mid - 1) && recur(mid, to - 1);
        }
    }
    
    class fufei1 {
        public boolean verifyPostorder(int[] postorder) {
            return recur(postorder, 0, postorder.length - 1);
        }
        boolean recur(int[] postorder, int i, int j) {
            if (i >= j) return true;
            int p = i;
            while (postorder[p] < postorder[j]) p++;
            int mid = p;
            while (postorder[p] > postorder[j]) p++;
            return p == j && recur(postorder, i, mid - 1) && recur(postorder, mid, j - 1);
        }
    }
    
    /**
     * 路子太野了 直接看答案不可能看懂
     * */
    class crazy {
    
        public boolean verifyPostorder(int[] postorder) {
            LinkedList<Integer> stack = new LinkedList<>();
            int root = Integer.MAX_VALUE;
            for (int i = postorder.length - 1; i >= 0; i--) {
                int cur = postorder[i];
                if (cur > root) return false;
                while (!stack.isEmpty() && stack.peek() > cur) root = stack.pop();
                stack.push(cur);
            }
            return true;
        }
    }
}
